In wireless communication systems, the RF channel resource may be viewed as a slice of the frequency-time plane, as shown in FIG. 1. The objective of the multiple-access protocol is the division of this resource among the users of the channel (who are referred to as nodes) in a manner that provides acceptable (or, ideally, optimal) performance. Common multiple access methods are TDMA (Time Division Multiple Access), FDMA (Frequency Division Multiple Access), and CDMA (Code Division Multiple Access).
Under TDMA, the channel resource is divided into time slots. For example, in a system with N users, the time axis would be divided into periodically recurring frames of length N slots, with one user assigned to each slot. Each slot uses the entire bandwidth assigned to the channel. Thus, one slot is available to each user in every frame, without the possibility of contention from other users. Under FDMA, the available frequency band is divided into frequency bands. For example, in a system with N users, the frequency band would be divided into N sub-bands, with each user assigned to its own band on a continuous basis. Again, there is no contention for channel use because the users transmit in distinct frequency bands. Under CDMA, the users are assigned pseudo-orthogonal spreading codes, thus permitting the successful simultaneous transmission of several signals.
In a time-slotted system, a packet is received successfully (with high probability) if the signal-to-interference ratio at the destination node is sufficiently high. The source of such interference may be background noise, jamming, other-user interference, etc. In this discussion, we assume that the only significant source of interference is other-user interference (i.e., background noise and other sources of interference are negligible).
When TDMA is used, there is no other-user interference because each user is assigned its own periodically recurring time slot. TDMA can provide a throughput of one packet per slot if each user generates traffic at a constant rate of one packet per frame. Delay is proportional to the number of users (and hence to the number of slots per frame). TDMA is inefficient when traffic is randomly generated, e.g., according to a Poisson process, because many slots will be left unused while some users may have several packets waiting for transmission.
Moreover, TDMA does not take advantage of the possibility of geographically separated users (who are too far apart to cause interference) transmitting in the same slot. Therefore, TDMA is inefficient in networks that have multiple destinations that are geographically separated. The terminology “multihop network” as used herein refers to such networks. Spatial TDMA approaches, which permit simultaneous transmissions to geographically separated destinations, can provide acceptable performance when the traffic is generated at a fixed rate at each node. However, when traffic is random (e.g., generated according to a Poisson process at each node) and the number of nodes is large, this approach is characterized by low throughput and large delay.
A variety of multiple-access protocols have been developed to address the medium access control (MAC) problem for applications where traffic is randomly generated. Among the best known of these are the random access protocols known as slotted Aloha and the first-come first-serve (FCFS) collision-resolution algorithm (CRA). These protocols were originally developed for single-destination systems. Random-access protocols are MAC protocols that do not assign users to slots. These instead use a contention-based mechanism, under which destructive interference (known as a collision) occurs when two or more nodes transmit in the same slot. None of the packets involved in a collision are successfully received, and all must be transmitted in future slots. Slotted Aloha can provide a throughput of 1/e=0.368 packet/slot in a large population of bursty users, and can be stabilized to maintain this throughput level, even when the offered traffic load is greater than this value. The FCFS algorithm, which is inherently stable in single-destination systems, can provide a throughput of 0.4878 packet/slot when two well-known “improvements” are used.
“Slotted Aloha” is a random-access MAC scheme in which the users are not assigned slots. In stabilized versions of slotted Aloha, a user with a packet to transmit will do so with a probability that is typically based on recent channel feedback, i.e., whether recent slots were empty, successful transmissions (i.e., exactly one user transmitted in the slot), or collisions (two or more users transmitted in the slot). When such collisions occur, none of the packets involved in the collision are successful; therefore they must be retransmitted. It is assumed throughout this document, for all random-access protocols that are discussed, that accurate channel feedback concerning the outcome of each slot is available to all network nodes immediately following the slot.
The “First-Come First-Serve (FCFS)” collision-resolution algorithm (CRA) is another type of random-access scheme in which the users are not assigned slots. It differs fundamentally from slotted Aloha by its structured transmission policy, which is summarized as follows. All packets that arrived in some time interval (known as the “allocation interval”) are transmitted in some slot. If a collision occurs, the interval is split into two smaller subintervals, and the packets that arrived in the first subinterval are retransmitted in the next slot. This subinterval is further split if another collision results, and so on. A throughput of 0.4878 is realized by the FCFS splitting algorithm upon implementation of certain “improvements,” which are defined as follows.
The “first improvement” in FCFS addresses the case of a collision that is followed immediately by an idle slot. Straightforward application of the FCFS algorithm guarantees that a collision will occur in the next slot. To avoid such wasting of a slot, the algorithm acts as if the collision had already occurred, and shortens the allocation interval accordingly.
The “second improvement” (which has a somewhat smaller impact on achievable throughput than does the first improvement) incorporates the right (i.e., later) half of the allocation interval involved in the original collision into subsequent collision resolution periods. The combined effect of using both the first and second improvements provides a maximum stable throughput of about 0.4878. Use of the second improvement alone provides a maximum stable throughput of about 0.447.
The operation of slotted Aloha and CRAs heavily depends on the feedback information that each participating node receives from the destinations immediately after every slot. This feedback indicates whether the channel in the previous slot was idle, had a collision, or had successfully carried a packet. In multiple-destination networks, some nodes are within communication range of only one destination, while others may be within range of two or more destinations. Consequently, packets intended for one destination are subject to collisions with packets intended for one or more of the other destinations. In addition to this obvious increase in interference, feedback information can be misinterpreted because there is no way to identify the intended destination of a packet that suffers a collision.
FIG. 2 shows a network 10 with two destinations 12 and 14 (D1 and D2, respectively) and a number of nodes 16 that are within communication range of them (assuming the same fixed communication range for all nodes and the use of omnidirectional antennas). A first group 18 (“Group 1”) is the set of nodes within communication range of only D1; similarly a second group 20 (“Group 2”) is the set of nodes within range of only D2. A third group 22 (“Group 3”) is the set of nodes that are within range of both D1 and D2 (i.e., the intersection of the two circular regions). The discussion here is based on a simplified interference model in which a node can cause interference (i.e., a collision) only if it is within communication range. However, the concepts described below are applicable to any interference model.
Nodes in Group 1 randomly generate packets for transmission to D1; similarly nodes in Group 2 randomly generate packets for transmission to D2. Nodes in Group 3 randomly generate packets for transmission to either D1 or D2; once a destination is chosen for a particular packet, the packet must be delivered to that destination (i.e., no reward is received for successful reception at the wrong destination). Group 3 is subdivided into two parts: a fourth group 24 (“Group 31”) nodes are intended for D1 and a fifth group 26 (“Group 32”) nodes are intended for D2. Since packets from Group 3 reach both destinations, they are potentially a source of collisions at both the intended and nonintended destination. Therefore, throughput is reduced.
In view of the improved performance provided by FCFS over slotted Aloha, it would be desirable to be able to exploit this advantage in two-destination systems as well. However, the best version of FCFS (which incorporates the “first improvement” and “second improvement,” both of which were described earlier) is subject to a deadlock condition in two-destination or other multiple destination systems with overlapping user populations, as is discussed in J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “Multiple Access for Multiple Destinations in Ad Hoc Networks,” Proceedings of Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03), Sophia-Antipolis, FRANCE, Mar. 3–5, 2003, and in G. D. Nguyen, J. E. Wieselthier, and A. Ephremides, “Contention-Resolution Algorithms for Multiple Destinations in Wireless Networks,” Proceedings of the 2003 Conference on Information Sciences and Systems, Johns Hopkins University, Baltimore, Md., Mar. 12–14, 2003, both of which are incorporated herein by reference.
The “first improvement” makes the FCFS algorithm vulnerable to errors in the feedback process. Consider first the case of a single-destination network. For example, if an idle slot is erroneously interpreted as a collision, the allocation interval is then split because it is believed that a collision has occurred. However, since there are actually no packets in the allocation interval, the result is an empty slot. Use of the first improvement results in further reduction of the empty allocation interval, a process that continues indefinitely, resulting in deadlock.
Now consider Destination 1 in a multiple-destination system. Collisions of packets that are intended for another destination (or destinations) result in a collision being heard at Destination 1, even though no packets intended for Destination 1 were actually transmitted in that slot. Because of this collision, the allocation interval associated with Destination 1 is split indefinitely, as described above for the single-destination case, again resulting in deadlock.
When the first improvement is not used, splitting algorithms are extremely insensitive to feedback errors. In applications where such errors are rare, it may be appropriate to simply suspend the splitting of the interval after observing several such idle slots. However, it may be best not to use the first improvement at all when such errors are frequent. The case of multiple destinations creates a situation that is similar to that of frequent feedback errors. Therefore, the first improvement should not be used in multiple-destination networks that use a straightforward implementation of the FCFS algorithm, which we refer to as “free-running FCFS.” If the first improvement is not incorporated into the algorithm, the network is no longer subject to such deadlocks; however throughput is reduced to approximately 0.447 in single-destination networks (which is still higher than that of slotted Aloha).
There remains, therefore, a need to develop a channel-access protocol that can provide at least some of the benefits of the first improvement (specifically its increased throughput), without being vulnerable to the deadlock situation described above.